class Solution
{
public:
    int numTilings(int n)
    {
        constexpr int MOD = 1000000007;
        vector<vector<long long>> dp(n + 1, vector<long long>(4));
        dp[0][3] = 1;
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = dp[i - 1][3];
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
            dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD;
        }
        for (int i = 1; i <= n; ++i)
        {
            cout << dp[i][3] << ", ";
            if ((i) % 20 == 0)
            {
                cout << endl;
            }
        }
        return dp[n][3];
    }

    int numTilingsTable(int n)
    {
        vector<int> result{0, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255, 2768, 6105, 13465, 29698, 65501, 144467, 318632, 702765, 1549997, 3418626,
                           7540017, 16630031, 36678688, 80897393, 178424817, 393528322, 867954037, 914332884, 222194076, 312342182, 539017241, 300228551, 912799284, 364615795, 29460134, 971719552, 308054885, 645569904, 262859346, 833773577,
                           313117044, 889093434, 611960431, 537037899, 963169225, 538298867, 613635626, 190440463, 919179793, 451995198, 94430852, 108041490, 668078178, 430587201, 969215892, 606509948, 643607090, 256430058, 119370057, 882347204,
                           21124452, 161618961, 205585119, 432294690, 26208334, 258001787, 948298264, 922804855, 103611483, 155521223, 233847294, 571306071, 298133358, 830114010, 231534077, 761201512, 352517020, 936568117, 634337732, 621192477,
                           178953057, 992243846, 605680155, 390313360, 772870559, 151421259, 693155878, 159182301, 469785861, 632727593, 424637480, 319060814, 270849214, 966335908, 251732616, 774314446, 514964786, 281662181, 337638801, 190242381,
                           662146943, 661932680, 514107734, 690362404, 42657474, 599422682, 889207761, 821072989, 241568646, 372345046, 565763074, 373094787, 118534613, 802832300, 978759380, 76053359, 954939018, 888637402, 853328156, 661595316,
                           211828020, 276984189, 215563687, 642955394, 562894970, 341353620, 325662627, 214220217, 769794054, 865250728, 944721666, 659237372, 183725458, 312172575, 283582515, 750890488, 813953544, 911489596, 573869666, 961692869,
                           834875320, 243620292, 448933446, 732742205, 709104695, 867142829, 467027849, 643160386, 153463587, 773955023, 191070418, 535604423, 845163862, 881398135, 298400679, 441965213, 765328554, 829057780, 100080759, 965490072,
                           760037910, 620156572, 205803202, 171644307, 963445186, 132693560, 437031427, 837508033, 807709619, 52450651, 942409335, 692528275, 437507194, 817423716, 327375693, 92258573, 1940855, 331257403, 754773379, 511487606,
                           354232608, 463238588, 437964775, 230162151, 923562890, 285090541, 800343233, 524249342, 333589218, 467521662, 459292659, 252174529, 971870720, 403034085, 58242692, 88356097, 579746279, 217735243, 523826583, 627399438,
                           472534112, 468894800, 565189031, 602912167, 674719127, 914627278, 432166709, 539052538, 992732347, 417631389, 374315309, 741362958, 900357298, 175029891, 91422733, 83202757, 341435405, 774293543, 631789836, 605015070,
                           984323676, 600437174, 805889411, 596102484, 792642135, 391173667, 378449811, 549541750, 490257160, 358964124, 267469991, 25197135, 409358394, 86186772, 197570679, 804499752, 695186269, 587943210, 980386165, 655958585,
                           899860373, 780106897, 216172365, 332205096, 444517082, 105206522, 542618140, 529753355, 164713225, 872044590, 273842521, 712398267, 296841110, 867524741, 447447735, 191736573, 250997880, 949443495, 90623549, 432244978,
                           813933444, 718490430, 869225831, 552385092, 823260607, 515747031, 583879147, 991018894, 497784805, 579448750, 149916380, 797617565, 174683866, 499284112, 796185782, 767055423, 33394944, 862975670, 493006749, 19408435,
                           901792540, 296591815, 612592065, 126976656, 550545127, 713682312, 554341273, 659227666, 32137630, 618616533, 896460725, 825059073, 268734665, 433930048, 692919162, 654572982, 743076005, 179071158, 12715291, 768506587,
                           716084325, 444883934, 658274448, 32633207, 510150348, 678575137, 389783474, 289717289, 258009708, 905802890, 101323055, 460655818, 827114519, 755552086, 971759983, 770634471, 296821014, 565402004, 901438472, 99697944,
                           764797892, 431034242, 961766428, 688330734, 807695703, 577157820, 842646367, 492988423, 563134659, 968915678, 430819765, 424774182, 818464035, 67747821, 560269824, 939003676, 945755166, 451780142, 842563953, 630883058,
                           713546251, 269656441, 170195933, 53938110, 377532661, 925261255, 904460613, 186453873, 298168994, 500798594, 188051054, 674271102, 849340791, 886732629, 447736346, 744813476, 376359567, 200455473, 145724415, 667808397,
                           536072260, 217868928, 103546246, 743164752, 704198425, 511943089, 767050923, 238300257, 988543603, 744138115, 726576480, 441696549, 627531206, 981638885, 404974305, 437479809, 856598496, 118171283, 673822375, 204243232,
                           526657747, 727137862, 658518949, 843695638, 414529124, 487577190, 818850011, 52229132, 592035454, 2920905, 58070942, 708177338, 419275574, 896622090, 501421504, 422118575, 740859233, 983139963, 388398487, 517656200,
                           18452349, 425303185, 368262563, 754977475, 935258128, 238778805, 232535078, 400328277, 39435352, 311405782, 23139834, 85715020, 482835822, 988811478, 63337962, 609511746, 207834956, 479007874, 567527487, 342889923,
                           164787713, 897102913, 137095735, 438979183, 775061272, 687218272, 813415720, 401892698, 491003661, 795423035, 992738761, 476481169, 748385366, 489509479, 455500120, 659385599, 808280670, 72061446, 803508491, 415297638,
                           902656722, 608821921, 632941473, 168539654, 945901229, 524743917, 218027481, 381956184, 288656278, 795340037, 972636251, 233928766, 263197562, 499031368, 231991495, 727180552, 953392465, 138776411, 4733367, 962859199,
                           64494795, 133722957, 230305106, 525105007, 183932964, 598171034, 721447068, 626827093, 851825213, 425097480, 477022046, 805869298, 36836062, 550694170, 907257631, 851351317, 253396790, 414051204, 679453718, 612304219,
                           638659635, 956772981, 525850167, 690359962, 337492891, 200835942, 92031839, 521556569, 243949073, 579929985, 681416532, 606782130, 793494238, 268404994, 143592111, 80678453, 429761900, 3115904, 86910261, 603582422,
                           210280741, 507471743, 618525901, 447332536, 402136808, 422799510, 292931549, 987999906, 398799308, 90530158, 169060215, 736919738, 564369627, 297799462, 332518655, 229406930, 756613322, 845745292, 920897507, 598408322,
                           42561922, 6021344, 610451010, 263463935, 532949214, 676349431, 616162790, 765274787, 206898991, 29960765, 825196317, 857291618, 744543994, 314284291, 485860193, 716264373, 746813030, 979486246, 675236851, 97286718,
                           174059675, 23356194, 143999106, 462057887, 947471968, 38943028, 539943943, 27359840, 93662708, 727269359, 481898551, 57459803, 842188965, 166276467, 390012737, 622214432, 410705324, 211423378, 45061181, 500827686,
                           213078743, 471218667, 443265013, 99608762, 670436191, 784137388, 667883531, 6203239, 796543866, 260971249, 528145737, 852835333, 966641908, 461429539, 775694404, 518030702, 497490936, 770676269, 59383226, 616257388,
                           3191031, 65765288, 747787964, 498766952, 63299185, 874386334, 247539606, 558378397, 991143121, 229825834, 18030058, 27203230, 284232294, 586494646, 200192515, 684617324, 955729287, 111651075, 907919474, 771568221,
                           654787510, 217494480, 206557174, 67901851, 353298182, 913153538, 894208920, 141716008, 196585547, 287380007, 716476022, 629537584, 546455168, 809386351, 248310272, 43075705, 895537761, 39385780, 121847265, 139232284,
                           317850348, 757547961, 654328199, 626506739, 10561425, 675451049, 977408830, 965379078, 606209191, 189827198, 345033467, 296276118, 782379434, 909792328, 115860760, 14100947, 937994222, 991849197, 997799334, 933592876,
                           859034935, 715869190, 365331242, 589697412, 895264007, 155859242, 901415896, 698095785, 552050805, 5517492, 709130769, 970312336, 946142157, 601415069, 173142460, 292427070, 186269202, 545680864, 383788791, 953846784,
                           453374418, 290537620, 534922017, 523218445, 336974503, 208871016, 940960477, 218895443, 646661902, 234284267, 687463977, 21589842, 277463951, 242391872, 506373586, 290211116, 822814104, 152001780, 594214676, 11243442,
                           174488664, 943192004, 897627443, 969743543, 882679076, 662985581, 295714691, 474108451, 611202476, 518119636, 510347716, 631897901, 781915431, 74178564, 780255029, 342425475, 759029514, 298314043, 939053561, 637136622,
                           572587280, 84228107, 805592836, 183772938, 451773983, 709140795, 602054521, 655883018, 20906817, 643868155, 943619321, 908145452, 460159045, 863937404, 636020246, 732199530, 328336450, 292693139, 317585801, 963508052,
                           219709229, 757004259, 477516556, 174742334, 106488920, 690494396, 555731119, 217951151, 126396691, 808524501, 835000146, 796396976, 401318439, 637637017, 71670996, 544660431, 726957872, 525586733, 595833890, 918625645,
                           362838009, 321509901, 561645440, 486128882, 293767658, 149180749, 784490380, 862748411, 874677564, 533845494, 930439392, 735556334, 4958148, 940355688, 616267696, 237493533, 415342747, 446953183, 131399892, 678142531,
                           803238238, 737876361, 153895239, 111028709, 959933779, 73762783, 258554275, 477042322, 27847420, 314249115, 105540545, 238928510, 792106135, 689752808, 618434119, 28974359, 747701526, 113837157, 256648673, 260998865,
                           635834887, 528318440, 317635738, 271106356, 70531145, 458698028, 188502405, 447535955, 353769931, 896042267, 239620475, 833010881, 562064015, 363748498, 560507870, 683079748, 729907987, 20323830, 723727408, 177362789,
                           375049408, 473826217, 125015216, 625079840, 723985890, 572986989, 771053811, 266093498, 105173978, 981401767, 228897018, 562968014, 107337781, 443572580, 450113167, 7564108, 458700796, 367514752, 742593612, 943888013,
                           255290764, 253175133, 450238272, 155767301, 564709735, 579657735, 315082764, 194875256, 969408247, 253899244, 702673744, 374755721, 3410679, 709495102, 793745918, 590902508, 891300111, 576346126, 743594753, 378489603,
                           333325325, 410245396, 198980388, 731286101, 872817591, 944615563, 620517213, 113852003, 172319562, 965156337, 44164663, 260648888, 486454106, 17072868, 294794624, 76043347, 169159562, 633113748, 342270836, 853701234,
                           340516202, 23303233, 900307700, 141131588, 305566409, 511440511, 164012603, 633591615, 778623734, 721260064, 76111729, 930847192, 582954434, 242020590, 414888365, 412731157, 67482897, 549854159, 512439468, 92361826,
                           734577811, 981595083, 55551978, 845681767, 672958603, 401469177, 648620114, 970198824, 341866811, 332353729, 634906275, 611679354, 555712430, 746331128, 104341596, 764395622, 275122358, 654586312, 73568232, 422258822,
                           499103949, 71776123, 565811068, 630726078, 333228272, 232267605, 95261281, 523750834, 279769266, 654799813, 833350453, 946470165, 547740129, 928830704, 804131559, 156003233, 240837163, 285805878, 727614989, 696067134,
                           677940139, 83495253, 863057640, 404055405, 891606063, 646269752, 696594902, 284795853, 215861451, 128317797, 541431447, 298724338, 725766473, 992964386, 284653096, 295072658, 583109695, 450872479, 196817609, 976744913,
                           404362291, 5542184, 987829281, 380020839, 765583862, 518996991, 418014814, 601613483, 722223950, 862462707, 326538883, 375301709, 613066118, 552671112, 480643926, 574353963, 701379031, 883401981, 341157911, 383694846,
                           650791666, 642741236, 669177311, 989146281, 621033784, 911244872, 811636011, 244305792, 399856449, 611348902, 467003589, 333863620, 279076135, 25155852, 384175324, 47426776, 120009404, 624194132, 295815033, 711639470,
                           47473058, 390761149, 493161761, 33796573, 458354295, 409870344, 853537261, 165428803, 740727950, 334993147, 835415097, 411558130, 158109400, 151633890, 714825910, 587761213, 327156309, 369138521, 326038248, 979232805};
        return result[n];
    };
};